/*********************************************************************************************
 * Archivo: cannon.c
 *
 * Implementacion del algoritmo de Cannon para la multiplicacion de matrices
 * densas utilizando la Interfaz de Paso de Mensajes MPI, utilizando solo
 * las primitivas basicas MPI_Send y MPI_Recv.
 *
 * Para compilar:
 * gcc cannon.c -o cannon -I c:\ap -L c:\ap -lmpich
 *
 * Autores:
 * - Manuel Avalor. mavalosgodoy@gmail.com
 * - Arturo Ferreira. aferreiraduarte@gmail.com
 *
 * Alumnos de la Universidad Nacional de Asuncion - Facultad Politecnica.
 * Carrera: Ingenieria Informatica.
 * Materia: Electiva V - Algoritmos Paralelos.
 * Profesor: Cristian Von Lucken.
 * Anho: 2009.
 **********************************************************************************************/
#include <stdio.h>
#include "mpi.h"
#define n 400
#include <math.h>

int mi_id, rank_envio;
float A[n][n], B[n][n], C[n][n];
int coords[2], dims[2], periodos[2], coords_envio[2];


/******************************Funciones de MPI******************************/////



/**
 *Devuelve las coodenadas correspondiente a un rank especifico.
 *El vector de coordenas solo puede tener tamanho 2.
 *tamDim, es la longitud de la dimension del plano cartesiano cuadrado.
 */
void MPI_Cart_Coords(int tamDim, int rank, int *coords) {
    coords[0] = rank / tamDim;
    coords[1] = rank % tamDim;
}

/**
 *Devuelve el rank correspondiente a las coordenas recibidas como
 *parametros.
 *El vector de coordenas solo puede tener tamanho 2.
 */
void MPI_Cart_Rank(int tamDim, int *coords, int *rank) {
    *rank = tamDim * coords[0] + coords[1];
}

void MPI_Cart_Shift(int tamDim, int rank, int dir, int *fuente, int *destino) {
    int source[2];
    int dest[2];
    int coords[2];

    coords[0] = rank / tamDim;
    coords[1] = rank % tamDim;


    //Calculamos las coordenadas del origen.
    switch (dir){
        case 0:
            //Si queremos mover una fila.
            source[0] = coords[0];
            source[1] = coords[1] + 1;
            if (source[1] >= tamDim) {
                source[1] = source[1] - tamDim;
            }
            break;
        case 1:
            //Mover una columna
            source[1] = coords[1];
            source[0] = coords[0] + 1;
            if (source[0] >= tamDim) {
                source[0] = source[0] - tamDim;
            }
            break;
    }
    //Calculamos las coordenadas del destino.
    switch (dir){
        case 0:
            //Si queremos mover una fila.
            dest[0] = coords[0];
            dest[1] = coords[1] - 1;
            if (dest[1] < 0) {
                dest[1] = dest[1] + tamDim;
            }
            break;
        case 1:
            //Mover una columna
            dest[1] = coords[1];
            dest[0] = coords[0] - 1;
            if (dest[0] < 0) {
                dest[0] = dest[0] + tamDim;
            }
            break;
    }




    //Convertimos las coordenadas a ranks.
    *fuente = tamDim * source[0] + source[1];
    *destino = tamDim * dest[0] + dest[1];

}

/******************************Funciones Complementarias ******************************/
void llenarMatriz(float m[n][n]) {
    static float k = 0;
    int i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            m[i][j] = k++;
}

void imprimirMatriz(float m[n][n]) {
    int i, j = 0;
    for (i = 0; i < n; i++) {
        printf("\n\t| ");
        for (j = 0; j < n; j++)
            printf("%2f ", m[i][j]);
        printf("|");
    }
}

void imprimirSubMatriz(float m[3][3]) {
    int i, j = 0;
    for (i = 0; i < 3; i++) {
        printf("\n\t| ");
        for (j = 0; j < 3; j++)
            printf("%2f ", m[i][j]);
        printf("|");
    }
}


/****************************** MAIN ******************************/////
int main(int argc, char** argv) {
    /*DEFINICIONES DE DATOS E INICIALIZACIONES*/
    int mi_fila, mi_columna, fila_recepcion, col_recepcion;
    double timeIni, timeFin;
    int rank_envio, size, destino, fuente;
    int i, j, k, l,h,z, cont_fila, cont_columna, ciclos;
    FILE *fp;
    MPI_Status statusA;
    MPI_Status statusB;
    MPI_Status statusC;



    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &mi_id);
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    double m = pow((double) size, (double) 1 / 2);
    if (n % (int)m != 0) {
        printf("\nERROR:Por favor corra con una cantidad de procesos multiplo de %d.\n", n);
        fflush(stdout);
        MPI_Abort(MPI_COMM_WORLD, 1);
    } else if (m-(int)m != 0) {
        printf("\nERROR:Por favor corra con una cantidad de procesos con raiz cuadrada exacta...\n");
        fflush(stdout);
        MPI_Abort(MPI_COMM_WORLD, 1);
    }

    int tam_subM = n / m;
    //printf("EL VALOR M ES: %d", (int) m);
    //printf("EL VALOR TAMSUBM ES: %d", (int) tam_subM);
    dims[0] = dims[1] = (int) m;
    periodos[0] = periodos[1] = 1;

    float subm_A[tam_subM][tam_subM];
	float subm_A_aux[tam_subM][tam_subM];

	float subm_B[tam_subM][tam_subM];
	float subm_B_aux[tam_subM][tam_subM];

	float subm_C[tam_subM][tam_subM];
    float subm_C_aux[tam_subM][tam_subM];

    /* Obtiene mis coordenadas */
    MPI_Cart_Coords(m, mi_id, coords);

    mi_fila = coords[0];
    mi_columna = coords[1];

    //printf("\nSoy %d y mi coordenada x es %d\n",mi_id,mi_fila);
    //printf("\nSoy %d y mi coordenada y es %d\n",mi_id,mi_columna);

    /*inicializamos submatriz C*/
    for (i = 0; i < tam_subM; i++) {
        for (j = 0; j < tam_subM; j++) {
            subm_C[i][j] = 0;
        }
    }

    if (mi_id == 0) {
        llenarMatriz(A);
        llenarMatriz(B);

        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                C[i][j] = 0;
            }
        }

        printf("\n");

        /*Ahora basicamente lo que hacemos es enviar a cada proceso del plano cero
        una parte de A y B que es la que les corresponde, enviamos a cada uno ya con la distribución
        inicial para que puedan empezar multiplicando*/
        timeIni = MPI_Wtime();
        for (i = 0; i < m; i++) {
            for (j = 0; j < m; j++) {
                if (!(i == 0 && j == 0))
                {
                    coords_envio[0] = i;
                    coords_envio[1] = j;
                    cont_fila = -1;
                    for (k = i * tam_subM; k < i * tam_subM + tam_subM; k++) {
                        cont_fila++;
                        cont_columna = 0;
                        for (l = j * tam_subM; l < j * tam_subM + tam_subM; l++) {
                            subm_A[cont_fila][cont_columna] = A[k][l];
                            subm_B[cont_fila][cont_columna] = B[k][l];
                            cont_columna++;
                        }
                    }
                    /*calculamos el envio para A*/
                    /*Lo que se hace es modificar la coordenada referente
                    a la columna para enviar A al Pi,j que corresponde y luego
                    en la recepcion ya puede proceder directamente a la multiplicacion*/
                    coords_envio[0] = i;
                    coords_envio[1] = j - i;
                    if (coords_envio[1] < 0) {
                        coords_envio[1] = coords_envio[1] + m;
                    }
                    MPI_Cart_Rank(m, coords_envio, &rank_envio);

                    //printf("\nSoy 0 y (i, j) es (%d, %d)\n", i,j);
                    //printf("\nSoy 0 y le envio a %d\n", rank_envio);

                    MPI_Send(subm_A, (tam_subM * tam_subM), MPI_FLOAT, rank_envio, 1, MPI_COMM_WORLD);

                    /*calculamos el envio para B*/
                    /*Lo que se hace es modificar la coordenada referente
                    a la fila para enviar B al Pi,j que corresponde y luego
                    en la recepcion ya puede proceder directamente a la multiplicacion*/
                    coords_envio[1] = j;
                    coords_envio[0] = i - j;
                    if (coords_envio[0] < 0) {
                        coords_envio[0] = coords_envio[0] + m;
                    }
                    MPI_Cart_Rank(m, coords_envio, &rank_envio);
					//printf("\nSoy 0 y le envio a %d\n", rank_envio);
                    MPI_Send(subm_B, (tam_subM * tam_subM), MPI_FLOAT, rank_envio, 2, MPI_COMM_WORLD);
                }
            }
        }
        /*CARGO lo QUE CORRESPONDE AL PROCESO 0*/
        for (k = 0; k < tam_subM; k++) {
            for (l = 0; l < tam_subM; l++) {
                subm_A[k][l] = A[k][l];
                subm_B[k][l] = B[k][l];
            }
        }
        /*RESUELVO LA PARTE DE LA MATRIZ QUE SE ME QUEDO
        EN EL PROCESO 0*/

        for (ciclos = 0; ciclos < tam_subM; ciclos++) {
            for (i = 0; i < tam_subM; i++) {
                for (j = 0; j < tam_subM; j++) {
                    for (k = 0; k < tam_subM; k++) {
                        subm_C[i][j] += subm_A[i][k] * subm_B[k][j];
                    }
                }
            }
            MPI_Cart_Shift(m, mi_id , 0, &fuente, &destino);
            //printf("\nSoy 0, mi fuente es %d y mi destino es %d\n", fuente,destino);
            MPI_Send(subm_A, (tam_subM * tam_subM), MPI_FLOAT, destino, 1, MPI_COMM_WORLD);
			printf("\nSoy 0, mi fuente es %d y mi destino es %d\n", fuente,destino);
            MPI_Recv(subm_A, tam_subM*tam_subM, MPI_FLOAT, fuente, 1, MPI_COMM_WORLD, &statusA);

            MPI_Cart_Shift(m, mi_id , 1, &fuente, &destino);
            printf("\nSoy %d, mi fuente es %d y mi destino es %d\n",mi_id, fuente,destino);
            MPI_Send(subm_B, (tam_subM * tam_subM), MPI_FLOAT, destino, 2, MPI_COMM_WORLD);
            MPI_Recv(subm_B, tam_subM*tam_subM, MPI_FLOAT, fuente, 2, MPI_COMM_WORLD, &statusB);

        }

    } else {
        /*LOS OTROS PROCESOS RECIBEN SUS VALORES Y VAN HACIENDO SHIFT Y ENVIANDO A LOS DEMAS PARA
        QUE CADA UNO COMPUTE SU PARTE*/
		for (i = 0; i < m; i++) {
            for (j = 0; j < m; j++) {
				if (!(i == 0 && j == 0)){
					coords_envio[0] = i;
                    coords_envio[1] = j - i;
                    if (coords_envio[1] < 0) {
                        coords_envio[1] = coords_envio[1] + m;
                    }
                    MPI_Cart_Rank(m, coords_envio, &rank_envio);
					if(rank_envio == mi_id){
						MPI_Recv(subm_A, tam_subM*tam_subM, MPI_FLOAT, 0, 1, MPI_COMM_WORLD, &statusA);
					}

					coords_envio[1] = j;
                    coords_envio[0] = i - j;
                    if (coords_envio[0] < 0) {
                        coords_envio[0] = coords_envio[0] + m;
                    }
					MPI_Cart_Rank(m, coords_envio, &rank_envio);
					if(rank_envio == mi_id){
						MPI_Recv(subm_B, tam_subM*tam_subM, MPI_FLOAT, 0, 2, MPI_COMM_WORLD, &statusB);
					}
				}
			}
		}

        //printf("\nSoy %d y acabo de recibir mis bloques de 0\n",mi_id);

        for (ciclos = 0; ciclos < tam_subM; ciclos++) {
            for (i = 0; i < tam_subM; i++) {
                for (j = 0; j < tam_subM; j++) {
                    for (k = 0; k < tam_subM; k++) {
                        subm_C[i][j] += subm_A[i][k] * subm_B[k][j];
                    }
                }
            }
            MPI_Cart_Shift(m, mi_id , 0, &fuente, &destino);

			if(mi_columna==0)
			{
				MPI_Send(subm_A, (tam_subM * tam_subM), MPI_FLOAT, destino, 1, MPI_COMM_WORLD);
				printf("\nSoy %d, mi fuente es %d y mi destino es %d\n",mi_id, fuente,destino);
				MPI_Recv(subm_A, tam_subM*tam_subM, MPI_FLOAT, fuente, 1, MPI_COMM_WORLD, &statusA);
			}else
			{

				MPI_Recv(subm_A_aux, tam_subM*tam_subM, MPI_FLOAT, fuente, 1, MPI_COMM_WORLD, &statusA);
				printf("\nSoy %d, mi fuente es %d y mi destino es %d\n",mi_id, fuente,destino);
				MPI_Send(subm_A, (tam_subM * tam_subM), MPI_FLOAT, destino, 1, MPI_COMM_WORLD);
				//Copiamos el contenido de nuestro buffer auxiliar
				for(h=0;h<tam_subM;h++)
				{
					for(z=0;z<tam_subM;z++)
					{
						subm_A[h][z]= subm_A_aux[h][z];
					}
				}
			}



            MPI_Cart_Shift(m, mi_id , 1, &fuente, &destino);
			if(mi_fila==0)
			{
				MPI_Send(subm_B, (tam_subM * tam_subM), MPI_FLOAT, destino, 2, MPI_COMM_WORLD);
				printf("\nSoy %d, mi fuente es %d y mi destino es %d\n",mi_id, fuente,destino);
				MPI_Recv(subm_B, tam_subM*tam_subM, MPI_FLOAT, fuente, 2, MPI_COMM_WORLD, &statusB);
			}else
			{
				MPI_Recv(subm_B_aux, tam_subM*tam_subM, MPI_FLOAT, fuente, 2, MPI_COMM_WORLD, &statusB);
				printf("\nSoy %d, mi fuente es %d y mi destino es %d\n",mi_id, fuente,destino);
				MPI_Send(subm_B, (tam_subM * tam_subM), MPI_FLOAT, destino, 2, MPI_COMM_WORLD);
				//Copiamos el contenido de nuestro buffer auxiliar
				for(h=0;h<tam_subM;h++)
				{
					for(z=0;z<tam_subM;z++)
					{
						subm_B[h][z]= subm_B_aux[h][z];
					}
				}
			}


        }

        /*AHORA LO QUE HACEMOS ES ENVIAR AL PROCESO MAESTRO EL RESULTADO FINAL QUE OBTUVIMOS PARA NUESTRA
        SUBMATRIZ C*/
        MPI_Send(subm_C, tam_subM*tam_subM, MPI_FLOAT, 0, mi_id, MPI_COMM_WORLD);
    }

    if (mi_id == 0) {
        printf("\nSi entra...\n");
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                C[i][j] = 0;
            }
        }
        /*RECIBIMOS Y ESTABLECEMOS CADA SUBMATRIZ C EN LA PARTE QUE CORRESPONDE*/
        for (i = 1; i < size; i++) {

            MPI_Recv(subm_C_aux, tam_subM*tam_subM, MPI_FLOAT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &statusC);
            MPI_Cart_Coords(m, statusC.MPI_TAG,coords_envio);

            //imprimirSubMatriz(subm_C_aux);
            fila_recepcion = coords_envio[0];
            col_recepcion = coords_envio[1];
            cont_columna = 0;
            cont_fila = -1;
            for (j = fila_recepcion * tam_subM; j < fila_recepcion * tam_subM + tam_subM; j++) {
                cont_fila++;
                for (k = col_recepcion * tam_subM; k < col_recepcion * tam_subM + tam_subM; k++) {
                    C[j][k] = subm_C_aux[cont_fila][cont_columna];
                    cont_columna++;
                }
                cont_columna = 0;
            }
        }
        /*AHORA ESTABLECEMOS LO QUE COMPUTO EL PROCESO 0*/
        for (k = 0; k < tam_subM; k++) {
            for (l = 0; l < tam_subM; l++) {
                C[k][l] = subm_C[k][l];
            }
        }
        printf("INICIAMOS IMPRESIÓN A ARCHIVO...\n");
        timeFin = MPI_Wtime();

        if ((fp = freopen("ResultadosCannon.txt", "w", stdout)) == NULL) {
            printf("NO PUEDO ABRIR ARCHIVO.\n");
            exit(1);
        }
        printf("TIEMPO TARDADO---> %f segundos\n", timeFin - timeIni);
        printf("IMPRESION DE LA MATRIZ A\n.");
        imprimirMatriz(A);
        printf("IMPRESION DE LA MATRIZ B\n.");
        imprimirMatriz(B);

        printf("IMPRESION FINAL DE LA MATRIZ C\n.");
        imprimirMatriz(C);
        fclose(fp);
        //imprimirMatriz(C);
    }

    MPI_Finalize();
}

